#include <iostream>
using namespace std;

int minDistance(string word1, string word2) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int length1 = word1.size();
    int length2 = word2.size();

    if(length1 == 0)
        return length2;
    if(length2 == 0)
        return length1;

    int *pDisRead = new int[length1+1];
    int *pDisWrite = new int[length1+1];
    // init pDis
    for(int i=0; i<=length1; ++i){
        pDisRead[i] = i;
    }
    // do iteration
    for(int j=1; j<=length2; ++j){
        pDisWrite[0] = j;
        for(int i=1; i<=length1; ++i){
            int insert = pDisWrite[i-1] + 1;
            int remove = pDisRead[i] + 1;
            int replace = word1[i-1] == word2[j-1] ? pDisRead[i-1] : (pDisRead[i-1]+1);
            int iOr = (insert > remove? remove : insert);
            pDisWrite[i] = iOr > replace ? replace : iOr;
        }
        int *pTemp = pDisWrite;
        pDisWrite = pDisRead;
        pDisRead = pTemp;
    }
    // output
    int res = pDisRead[length1];

    delete []pDisRead;
    delete []pDisWrite;

    return res;
}

int main(){

    cout<<minDistance("abc","a")<<endl;;

    return 0;
}

